import java.util.Stack;

public class Test {

    //括号匹配
    public boolean isValid(String s){
        Stack<Character> satck = new Stack<>();//new一个栈出来
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);//每次获取一个字符
            if(ch == '(' || ch =='{' || ch == '['){//满足条件放到栈里面
                satck.push(ch);
            }else{ //不是左括号，就是遇到右括号
                if(satck.isEmpty()){//如果栈是空的
                    return false;
                }
                //此是开始判断是否匹配
                char ch2 = satck.peek();//获取栈顶元素
                if(ch == ')' && ch2 == '(' || ch == '}' && ch2 == '{'||ch == ']' && ch2 == '[' ){//括号匹配就出栈
                    satck.pop();
                }else {
                    return false;
                }
            }
        }
        if(!satck.isEmpty()){
            return false;
        }
        return true;

    }


    //给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    public int evalPRN(String[] tokens){
        Stack<Integer> stack = new Stack<>();//创建一个栈将数值存入栈中
        for (String str : tokens){
            if(!isOperator(str)){//如果不是运算符,是数字
                int x = Integer.parseInt(str);//把一个字符串变成一个整数
                stack.push(x);
            }else {//是运算符
                int val2 = stack.pop();//取出栈顶元素
                int val1 = stack.pop();
                switch (str){//判断表达式
                    case "+" :
                        stack.push(val1 + val2);//运算完直接放进栈里面
                        break;
                    case "-" :
                        stack.push(val1 - val2);//运算完直接放进栈里面
                        break;
                    case "*" :
                        stack.push(val1 * val2);//运算完直接放进栈里面
                        break;
                    case "/" :
                        stack.push(val1 / val2);//运算完直接放进栈里面
                        break;
                }
            }
        }
        return stack.pop();//将最后的结构出栈
    }

    private  boolean isOperator(String str){//判断是不是操作符
        if(str.equals("+") ||str.equals("-")||str.equals("*")||str.equals("/")){
            return  true;
        }
        return false;
    }

    //栈的压入、弹出序列
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();//创建一个栈
        int j = 0;
        for(int i = 0; i < pushV.length;i++){
            stack.push(pushV[i]);
            while (!stack.empty() && stack.peek() == popV[j] && j < popV.length){//栈不为空，j没有超出范围，栈顶元素和popV[j]一样
                stack.pop();
                j++;
            }
        }
        return stack.empty();

    }
}
class MinStack {
    public Stack<Integer> stack;
    public Stack<Integer> minStack;

    //MinStack() 初始化堆栈对象。
    public MinStack() {
         stack = new Stack<>();//定义一个普通栈
         minStack = new Stack<>() ;//定义一个最小栈
    }

    //void push(int val) 将元素val推入堆栈。
    public void push(int val) {
        stack.push(val);//普通栈一定要push一个val
        if(minStack.empty()){//如果最小栈为空
            minStack.push(val);//将数据放到最小栈里面
        }else{//最小栈不为空
            int pekval = minStack.peek();//获取最小栈的栈顶元素
            if(val <= pekval){
                minStack.push(val);//如果小于或者等于最小栈的栈顶元素，将数据放进来
            }
        }
    }

    //void pop() 删除堆栈顶部的元素。
    public void pop() {
        if(stack.empty()){//如果普通栈为空直接返回
            return;
        }
        //不为空就直接出栈
        int popval = stack.pop();//先拿到普通栈的栈顶元素
        if(popval == minStack.peek()){//如果普通栈的栈顶元素等于最小栈的栈顶元素
            minStack.pop();//最小栈的栈顶元素出栈
        }

    }
    //获取普通栈的栈顶元素
    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }

    //int getMin() 获取堆栈中的最小元素。
    public int getMin() {
        if(minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }
}


